Một chuỗi nhị phân được gọi là ngẫu nhiên nếu độ phức tạp Kolmogorov của chuỗi ít nhất là độ dài của chuỗi. Một đối số đếm đơn giản cho thấy rằng một số chuỗi có độ dài bất kỳ là ngẫu nhiên và hầu như tất cả các chuỗi đều rất gần với ngẫu nhiên. Do độ phức tạp Kolmogorov phụ thuộc vào sự lựa chọn cố định của máy Turing phổ dụng (không chính thức, một "ngôn ngữ mô tả" cố định trong đó "mô tả" được đưa ra), nên bộ sưu tập các chuỗi ngẫu nhiên phụ thuộc vào sự lựa chọn của máy vạn năng cố định. Tuy nhiên, toàn bộ tập hợp các chuỗi ngẫu nhiên, có các thuộc tính tương tự bất kể máy cố định, vì vậy người ta có thể (và thường không) nói về các thuộc tính của chuỗi ngẫu nhiên như một nhóm mà không cần phải chỉ định trước một máy phổ quát.

Một chuỗi nhị phân vô hạn được gọi là ngẫu nhiên nếu, đối với một số hằng số c, với mọi n, độ phức tạp Kolmogorov của đoạn ban đầu có độ dài n của chuỗi ít nhất là n   -   c. Có thể chỉ ra rằng hầu hết mọi chuỗi (theo quan điểm của thước đo tiêu chuẩn - "đồng tiền công bằng" hoặc thước đo Lebesgue, không gian của chuỗi nhị phân vô hạn) là ngẫu nhiên. Ngoài ra, vì có thể chỉ ra rằng độ phức tạp Kolmogorov so với hai máy vạn năng khác nhau khác nhau nhiều nhất là một hằng số, tập hợp các chuỗi vô hạn ngẫu nhiên không phụ thuộc vào sự lựa chọn của máy vạn năng (trái ngược với chuỗi hữu hạn). Định nghĩa về tính ngẫu nhiên này thường được gọi là tính ngẫu nhiên của Martin-Löf, sau Per Martin-Löf, để phân biệt nó với các khái niệm ngẫu nhiên tương tự khác. Đôi khi nó còn được gọi là ngẫu nhiên 1 để phân biệt với các khái niệm ngẫu nhiên mạnh hơn khác (2 ngẫu nhiên, 3 ngẫu nhiên, v.v.). Ngoài các khái niệm ngẫu nhiên Martin-Löf, còn có các ngẫu nhiên đệ quy, ngẫu nhiên Schnorr và ngẫu nhiên Kurtz, v.v. Yongge Wang đã chỉ ra [5] rằng tất cả các khái niệm ngẫu nhiên này là khác nhau.